{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "# Solving Mountain Car with SVP\n",
    "\n",
    "This notebook shows how to use the proposed structured value-based planning (SVP) approach to generate the state-action $Q$-value function for the classic mountain car problem. The correctness of the solution is verified by trajectory simulations."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "## Problem Definition\n",
    "\n",
    "In this problem, an under-powered car aims to drive up a steep hill. The physical dynamics of the system is described by the  position and the velocity, i.e., $\\left(x, \\dot{x}\\right)$. Denote $u$ as the acceleration input on the car, the dynamics can be written as\n",
    "\n",
    "\\begin{align}\n",
    "    & x := x + \\dot{x},\\\\\n",
    "    & \\dot{x} := \\dot{x} - 0.0025\\cos{(3x)} + 0.001u.\n",
    "\\end{align}\n",
    "\n",
    "The reward function is defined to encourage the car to get onto the top of the mountain at $x_0=0.5$:\n",
    "\n",
    "\\begin{equation}\n",
    "r(x) = \\left\\{\n",
    "\\begin{aligned}\n",
    "10, & \\qquad x\\ge x_0,\\\\\n",
    "-1, & \\qquad else.\n",
    "\\end{aligned}\n",
    "\\right.\n",
    "\\end{equation}\n",
    "\n",
    "We follow standard settings to restrict the state space as $\\left[-0.07, 0.07 \\right]$ for $x$ and $\\left[-1.2, 0.6 \\right]$ for $\\dot{x}$, and limit the input $u\\in[-1,1]$. Similarly, the whole state space is discretized into 2500 values, and the action space is discretized into 1000 values. The evaluation metric we are concerned about is the total time it takes to reach the top of the mountain, given a randomly and uniformly generated initial state."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "## Structured Value-based Planning (SVP)\n",
    "\n",
    "The proposed structured value-based planning (SVP) approach is based on the $Q$-value iteration. At the $t$-th iteration, instead of a full pass over all state-action pairs:\n",
    "- SVP first randomly selects a subset $\\Omega$ of the state-action pairs. In particular, each state-action pair in $\\mathcal{S}\\times\\mathcal{A}$ is observed (i.e., included in $\\Omega$) independently with probability $p$. \n",
    "- For each selected $(s,a)$, the intermediate $\\hat{Q}(s,a)$ is computed based on the $Q$-value iteration: \n",
    "    \\begin{equation*}\\hat{Q}(s,a) \\leftarrow \\sum_{s'} P(s'|s,a) \\left( r(s,a) + \\gamma \\max_{a'} Q^{(t)}(s',a') \\right),\\quad\\forall\\:(s,a)\\in\\Omega.\n",
    "    \t\t\t\t\\end{equation*}\n",
    "- The current iteration then ends by reconstructing the full $Q$ matrix with matrix estimation, from the set of observations in $\\Omega$. That is, $Q^{(t+1)}=\\textrm{ME}\\big(\\{\\hat{Q}(s,a)\\}_{(s,a)\\in\\Omega}\\big).$\n",
    "\n",
    "Overall, each iteration reduces the computation cost by roughly $1-p$."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "source": [
    "Through SVP, we can compute the final state-action $Q$-value function.\n",
    "To obtain the optimal policy for state $s$, we compute\n",
    "\n",
    "\\begin{align*}\n",
    "    \\pi^{\\star} \\left(s\\right) = \\mbox{argmax}_{a \\in \\mathcal{A}} Q^{\\star}\\left(s, a\\right).\n",
    "\\end{align*}"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "### Generate state-action value function with SVP"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "scrolled": true,
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [],
   "source": [
    "push!(LOAD_PATH, \".\")\n",
    "using MDPs, MountainCar\n",
    "mdp = MDP(state_space(), action_space(), transition, reward)\n",
    "__init__()\n",
    "policy = value_iteration(mdp, true, \"../data/qmc_otf_0.4.csv\", true)\n",
    "print(\"\")  # suppress output"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "### Visualize policy as a heat map"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [
    {
     "name": "stderr",
     "output_type": "stream",
     "text": [
      "┌ Info: Precompiling ImageMagick [6218d12a-5da1-5696-b52f-db25d2ecc6d1]\n",
      "└ @ Base loading.jl:1187\n"
     ]
    }
   ],
   "source": [
    "viz_policy(mdp, policy, \"SVP policy (40% observed)\", true, \"mc/policy_mc_0.4.tex\")"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "collapsed": true,
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "### Verify correctness\n",
    "Simulate and visualize trajectory from initial state `[position, speed]`."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [],
   "source": [
    "ss, as = simulate(mdp, policy, [-0.5, 0.0])\n",
    "viz_trajectory(ss, as, \"SVP policy trajectory (40% observed)\", \"SVP policy input (40% observed)\", true, \"mc/traj_mc_0.4.tex\")"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "average times: 58.424"
     ]
    },
    {
     "name": "stderr",
     "output_type": "stream",
     "text": [
      "WARNING: Base.@printf is deprecated: it has been moved to the standard library package `Printf`.\n",
      "Add `using Printf` to your imports.\n",
      "  likely near /home/yuzhe/.julia/packages/IJulia/gI2uA/src/kernel.jl:52\n"
     ]
    }
   ],
   "source": [
    "nsim = 1000\n",
    "times = 0\n",
    "for sim = 1:nsim\n",
    "    state = [rand(XMIN:0.001 * (XMAX - XMIN):XMAX), \n",
    "             rand(VMIN:0.001 * (VMAX - VMIN):VMAX)]\n",
    "    _, as = simulate(mdp, policy, copy(state))\n",
    "    times += length(as)\n",
    "end # for sim\n",
    "times /= nsim\n",
    "@printf(\"average times: %.3f\", times)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  }
 ],
 "metadata": {
  "celltoolbar": "Slideshow",
  "kernelspec": {
   "display_name": "Julia 0.7.0",
   "language": "julia",
   "name": "julia-0.7"
  },
  "language_info": {
   "file_extension": ".jl",
   "mimetype": "application/julia",
   "name": "julia",
   "version": "0.7.0"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 1
}
